package com.chj.jz.dp.class03;

public class Code06_BestTimetoBuyandSellStockIII {
	/**
	 * @param prices:
	 *            Given an integer array
	 * @return: Maximum profit
	 */
	public static int maxProfitIII(int[] prices) {
		// write your code here

		int n = prices.length;
		if (n == 0) {
			return 0;
		}

		int[][] f = new int[n + 1][5 + 1];
		int i, j;

		f[0][1] = 0;
		for (i = 2; i <= 5; i++) {
			f[0][i] = Integer.MIN_VALUE;
		}

		for (i = 1; i <= n; i++) {
			for (j = 1; j <= 5; j += 2) {
				f[i][j] = f[i - 1][j];
				if (j > 1 && i >= 2 && f[i - 1][j - 1] != Integer.MIN_VALUE) {
					f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + prices[i - 1] - prices[i - 2]);
				}
			}

			for (j = 2; j <= 5; j += 2) {
				f[i][j] = f[i - 1][j - 1];
				if (i >= 2 && f[i - 1][j] != Integer.MIN_VALUE) {
					f[i][j] = Math.max(f[i][j], f[i - 1][j] + prices[i - 1] - prices[i - 2]);
				}
			}
		}

		return Math.max(f[n][1], Math.max(f[n][3], f[n][5]));
	}

	public static void main(String[] args) {
		{
			int[] arr = new int[] { 4,4,6,1,1,4,2,5 };
			System.out.println(maxProfitIII(arr));
		}
//		{
//			int[] arr = new int[] { 1, 2, 3, 4, 5 };
//			System.out.println(maxProfitIII(arr));
//		}
//		{
//			int[] arr = new int[] { 5, 4, 3, 2, 1 };
//			System.out.println(maxProfitIII(arr));
//		}

	}
}
